// 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
// 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
// 注意：
// 1、被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
// 2、任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。
// 3、如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

function solve(board: string[][]): void {
  if (board.length < 1) {
    // 安全检测
    return;
  }
  const rows: number = board.length;// 取得行
  const cols: number = board[0].length;// 取得列
  // 第一遍搜索图-->找到所有的边界联通区域
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      let isEdge: boolean = 
        i === 0 || i === rows - 1 || j === 0 || j === cols - 1;
      if (isEdge && board[i][j] === "O") {// 如果找到边界存在“O”，进入深度优先搜索阶段
        solve_DFS(board, i, j);
      }
    }
  }
  // 第二遍遍历图-->填格子
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {// 先后顺序不能错
      if (board[i][j] === "O") board[i][j] = "X";
      if (board[i][j] === "#") board[i][j] = "O";
    }
  }
}
// 深度优先遍历搜索
function solve_DFS(board: string[][], currRow: number, currCol: number) {
  let outEdge: boolean =
    currRow < 0 ||
    currRow > board.length - 1 ||
    currCol < 0 ||
    currCol > board[0].length - 1;
  if (outEdge) return; // 边界检测
  if (board[currRow][currCol] === "#" || board[currRow][currCol] === "X") {
    // 遍历过或者不是我们想要的那就直接跳过
    return;
  }
  board[currRow][currCol] = "#"; // 标记成三方标记
  solve_DFS(board, currRow - 1, currCol);
  solve_DFS(board, currRow, currCol - 1);
  solve_DFS(board, currRow + 1, currCol);
  solve_DFS(board, currRow, currCol + 1);
}

// 这道题目也是一道比较典型的图的搜索的题目，考察搜索方法
// 首先考虑最简单的情况，如果图本身的边界位置全部都是“X”
// 那这道题目的算法其实只用遍历一边图，然后将图内的所有“O”换成“X”填充即可
// 所以事实上对这道题目构成影响的其实就是处于边界位置的这些“O”
// 以及与这些边界位置的“O”联通的“O”
// 我们分两遍来对这个图进行搜索，第一遍对图进行搜索要做的事情就是找到边界位置“O”以及连通“O”
// 因为这些“O”它们最终并不会被替换成“X”，我们先找到边界位置的“O”，然后以这个“O”为起点开始对四周进行深度优先搜索
// 深度优先搜索的过程我们将这些“O”替换成“#”，表示已经搜索过
// 而在第二遍搜索中，我们直接将所有的“O”替换成“X”就可以了（因为已经排除过边界和联通情况）
// 同时第二遍搜索的过程中我们再把“#”替换回原来的“O”，这样就完成了题目的要求。